10004 - Bicoloring/p10004.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4 using namespace std;
   5
   6 bool g[200][200]; //matriz de adyacencia del grafo
   7 bool bicolorable;
   8
   9 bool visiteEdge(const int &u, const int &v, vector<int> visitas){
  10   for (int i=0; i<visitas.size()-1; i++){
  11     if ((visitas[i] == u && visitas[i+1] == v ) || (visitas[i] == v && visitas[i+1] == u))
  12       return true;
  13   }
  14   return false;
  15 }
  16
  17 void bt(int nodo, const int &n, vector<int> visitados){
  18   if (!bicolorable) return;
  19   vector<int> vecinos;
  20   //find neighbours
  21   for (int i=0; i<n; ++i){
  22     if (g[nodo][i]) vecinos.push_back(i);
  23   }
  24   //backtrack for each neighbour
  25   for (int i=0; i<vecinos.size(); ++i){
  26     if (!visiteEdge(nodo, vecinos[i], visitados)){
  27       int k = -1;
  28       for (int j=0; j<visitados.size(); ++j){
  29         if (visitados[j] == vecinos[i]) k = j;
  30       }
  31       if (k > -1 && ((visitados.size() - k) % 2) == 1){
  32         /*it means I have already visited node vecinos[i], which is at position k
  33           of visitados, i.e, vecinos[i] = visitados[k]. It also means that I traveled
  34           an odd number of nodes to arrive to vecinos[i] again, which means the graph
  35           has an odd cycle and  thus is not bicolorable. */
  36         bicolorable = false;
  37       }
  38       vector<int> temp(visitados);
  39       temp.push_back(vecinos[i]);
  40       e[nodo][vecinos[i]] = e[vecinos[i]][nodo] = true;
  41       bt(vecinos[i], n, temp);
  42     }
  43   }
  44
  45 }
  46
  47 int main(){
  48   int n;
  49   cin >> n;
  50   while (n){
  51     //process case
  52     memset(g, 0, sizeof(g));
  53     bicolorable = true;
  54     int l;
  55     cin >> l;
  56     //read graph
  57     for (int i=0; i<l; ++i){
  58       int x, y;
  59       cin >> x >> y;
  60       g[x][y] = g[y][x] = true;
  61     }
  62
  63     for (int i=0; i<n; ++i){
  64       //bt starting at every node
  65       if (bicolorable){
  66         vector<int> visitados;
  67         visitados.push_back(i);
  68         bt(i, n, visitados);
  69       }
  70     }
  71     if (!bicolorable) cout << "NOT BICOLORABLE.\n";
  72     else cout << "BICOLORABLE.\n";
  73     cin >> n;
  74   }
  75   return 0;
  76 }